package __回溯算法

import "sort"

/*
https://leetcode.cn/problems/subsets-ii/

90. 子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：
输入：nums = [0]
输出：[[],[0]]
*/
var (
	path90 []int
	res90  [][]int
)

func subsetsWithDup(nums []int) [][]int {
	path90, res90 = make([]int, 0, len(nums)), make([][]int, 0)

	sort.Ints(nums)

	dfs90(nums, 0)
	return res90
}

func dfs90(nums []int, start int) {
	tmp := make([]int, len(path90))
	copy(tmp, path90)
	res90 = append(res90, tmp)

	for i := start; i < len(nums); i++ {
		if i != start && nums[i] == nums[i-1] {
			continue
		}
		path90 = append(path90, nums[i])
		dfs90(nums, i+1)
		path90 = path90[:len(path90)-1]
	}
}
